The study of graphs, or graph theory, is used in communications and information technology systems for various purposes. A graph refers to a collection of nodes (or vertices) and a collection of edges that connect pairs of nodes. A dominating set DS for a graph G is a set of nodes in G such that every node not in DS is joined to at least one member of DS by some edge. That is, each node in G is either a member of the dominating set DS or 1 hop away from a member node (may also be referred to as a dominating node). It is noted that a dominating set may include disjoint sets of nodes in the graph.
A connected dominating set (CDS) of a graph G includes a dominating set and a set of connecting nodes that may be needed to connect disjoint nodes in the dominating set. CDSs have traditionally been used in mobile ad-hoc networks for routing applications. For instance, broadcast and multicast protocols may efficiently reach all destinations by restricting transmissions to nodes that are members of the CDS (instead of every node in the graph). In addition to routing, mobile ad-hoc networks may benefit from CDSs in other areas including channel access, link adaptation, energy consumption, power control, dynamic resource management and the like.
Since a given graph may have more than one CDS, it may be beneficial to identify a CDS with minimum number of elements (e.g., nodes and/or edges). Such a CDS may be referred to as a minimum connected dominating set (MCDS). However, it has been shown that the computation complexity of minimum connected dominating set problem (MCDS), and minimum dominating set problem (MDS) in general, is NP-complete. Therein lies a need for a system and method capable of efficiently identifying a CDS with the number of elements as close to the minimum number as possible.